// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem1011.h"

using namespace std;
// @before-stub-for-debug-end

// @lcpr-before-debug-begin




// @lcpr-before-debug-end

/*
 * @lc app=leetcode.cn id=1011 lang=cpp
 * @lcpr version=30204
 *
 * [1011] 在 D 天内送达包裹的能力
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <numeric>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int low = *std::max_element(weights.begin(), weights.end());
        int hi = std::accumulate(weights.begin(), weights.end(), 0);
        while(low < hi){
            int res = (low + hi) >> 1;
            if (solve(weights, days, res)){
                hi = res;
            }else{
                low = res + 1;
            }
        }

        return (low + hi) >> 1;
    }
    bool solve(const vector<int>& weights, int days, int cap){
        int needDays = 1;
        int temp = 0;
        for(auto w : weights){
            temp += w;
            if (temp > cap){
                if (++needDays > days){
                    return false;
                }
                temp = w;
            }
        }
        return true;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [1,2,3,4,5,6,7,8,9,10]\n5
// @lcpr case=end

// @lcpr case=start
// [3,2,2,4,1,4]\n3\n
// @lcpr case=end

// @lcpr case=start
// [1,2,3,1,1]\n4\n
// @lcpr case=end

 */

